package tree;

import java.util.LinkedList;
import java.util.Queue;

//某公司架构以二叉树形式记录，请返回该公司的层级数。
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/7ffjqr/
public class 计算二叉树的深度 {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    /**
     * 树的遍历方式总体分为两类：
     * 深度优先搜索（DFS）： 先序遍历、中序遍历、后序遍历；
     * 广度优先搜索（BFS）： 层序遍历；
     */
    //后序遍历（DFS）
    class Solution {
        public int calculateDepth(TreeNode root) {
            if(root == null) return 0;
            return Math.max(calculateDepth(root.left),calculateDepth(root.right))+1;
        }
    }
    //层序遍历（BFS）
    class Solution2 {
        public int calculateDepth(TreeNode root) {
            if(root == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int res = 0;
            while (!queue.isEmpty()){
                Queue<TreeNode> tmp = new LinkedList<>();
                for(TreeNode node : queue){
                    if(node.left != null) tmp.add(node.left);
                    if(node.right!= null) tmp.add(node.right);
                }
                queue = tmp;
                res++;
            }
            return res;
        }
    }
}
